package ai.zixing.mashibing.basic_class.class07;

import java.util.Stack;

public class Code02_UnRecursiveTraversalBT {

    public static void pre(Node head) {
        System.out.println("pre-order: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            // 将头加入栈
            stack.push(head);
            while (!stack.isEmpty()) {
                head = stack.pop();
                System.out.println(head.value + " ");
                // 栈是先进后出，前序遍历左孩子线程，故先将右孩子入栈
                // 右孩子非空，则入栈
                if (head.right != null) {
                    stack.push(head.right);
                }
                // 左孩子非空，则入栈
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println();
    }

    public static void in(Node head) {
        System.out.println("pre-in: ");
        if (head != null) {
            Stack<Node> stack = new Stack<>();
            while (head != null || !stack.isEmpty()) {
                // 压入整个左边界
                if (head != null) {
                    stack.push(head);
                    head = head.left;
                } else {
                    // 左边界没有了，则弹出打印
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    // 查看右孩子
                    head = head.right;
                }
            }
        }
        System.out.println();
    }

    public static void pos1(Node head) {
        System.out.println("pre-pos1: ");
        if (head != null) {
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(head);
            while (!s1.isEmpty()) {
                head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.print(s2.pop().value + " ");
            }
        }
        System.out.println();
    }

    public static void pos2(Node h) {
        System.out.println("pre-pos2: ");
        if (h != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(h);
            Node c = null;
            while (!stack.isEmpty()) {
                c = stack.peek();
                // 在没有打印之前，h的指针没有意义，有打印后，h指向了打印的节点

                // c 有左孩子，且左孩子没有打印则左孩子入栈
                if (c.left != null && h != c.left && h != c.right) {
                    stack.push(c.left);
                }
                // c 有右孩子，且右孩子没有打印则右孩子入栈
                else if (c.right != null && h != c.right) {
                    stack.push(c.right);
                }
                // c 的左右孩子都遍历过，c出栈，并将 h 指向最新出栈的节点
                else {
                    System.out.println(stack.pop().value + " ");
                    // h 指向上次打印的节点
                    h = c;
                }
            }
        }
        System.out.println();
    }
}
